import numpy as np
import random

# Jeu de données : 5 documents, 3 termes (T1, T2, T3)
documents = [
    np.array([1, 3, 3]),   # d1
    np.array([2, 1, 0]),   # d2
    np.array([0, 1, 0]),   # d3
    np.array([1, 3, 1]),   # d4
    np.array([1, 0, 1]),   # d5
]


# Jeu de données étendu : 20 documents, 5 termes
# Groupe 1 (thématique 'sciences')  : termes T1, T2 prédominants
# Groupe 2 (thématique 'histoire')  : termes T3, T4 prédominants
# Groupe 3 (thématique 'sport')     : terme T5 prédominant
random.seed(42)
def doc_groupe(termes_forts, termes_faibles, p=5):
    v = np.zeros(p, dtype=int)
    for t in termes_forts:
        v[t] = random.randint(3, 7)
    for t in termes_faibles:
        v[t] = random.randint(0, 2)
    return v

documents_grands = (
    [doc_groupe([0,1],[2,3,4]) for _ in range(3)]   +  # sciences
    [doc_groupe([2,3],[0,1,4]) for _ in range(4)]   +  # histoire
    [doc_groupe([4],  [0,1,2,3]) for _ in range(6)] +  # sport
    [doc_groupe([2,3],[0,1,4]) for _ in range(4)]   +  # histoire
    [doc_groupe([0,1],[2,3,4]) for _ in range(3)]      # sciences
 )



############################
# ALGORITHME DES K MOYENNES
############################

# Question 3 : Fonction delta(di,dj)
def delta(di: np.ndarray, dj: np.ndarray) -> float:
    """
    Calcule la distance de Manhattan entre les vecteurs di et dj.
    Paramètres : di, dj — tableaux NumPy de même taille
    Retour     : float — somme des valeurs absolues des différences
    """
    distance_L1 = 0
    for j in range(len(di)):
        distance_L1 = distance_L1 + np.abs(di[j]-dj[j])
    return float(distance_L1)

# Tests de la question 3
print(delta(documents[0], documents[1]))  # Attendu : 6.0
print(delta(documents[1], documents[2]))  # Attendu : 2.0


# Question 4 : Fonction affectation
def affectation(documents: list, centres: list) -> list:
    """
    Retourne pour chaque document l'indice du centre le plus proche.
    Paramètres : documents — liste de vecteurs NumPy
                 centres  — liste de vecteurs NumPy (centres de classe)
    Retour     : list[int] — indices_centres_doc[i] = indice du centre le plus proche de documents[i]
    """
    indices_centres_documents = []

    for doc in documents:
        # Calcul des distances entre le document actuel (doc)
        # et les différents centres
        distances = [delta(doc,centres[i]) for i in range(len(centres))]

        # Récupère l'indice minimum
        indices_centres_documents.append(distances.index(min(distances)))

    return indices_centres_documents

# Tests de la question 4
c1 = documents[1]
c2 = documents[4]
print(affectation(documents,[c1,c2]))

# Question 5 : recalcul des centres
def recalcul_centres(documents: list, indices_centres: list, k: int) -> list:
    """
    Calcule les nouveaux centres de classe.
    Paramètres : documents       — liste de vecteurs NumPy
                 indices_centres — liste d'entiers (résultat de affectation)
                 k               — nombre de classes
    Retour     : list[np.ndarray] — nouveaux centres
    """
    nouveaux_centres = []

    # dimension des vecteurs
    p = len(documents[0])

    # Pour chaque classe
    for indice_classe in range(k):
        # Initialise le centre de la classe courante à 0
        centre_i = np.array([0 for i in range(p)])

        # Pour chaque vecteur appartenant à la classe courante
        # somme les vecteurs
        for indice_doc,doc in enumerate(documents):
            if indices_centres[indice_doc] == indice_classe:
                centre_i = centre_i + doc

        # Prend la moyenne de la somme des vecteurs
        centre_i = centre_i / indices_centres.count(indice_classe)

        # Ajoute le centre de la classe courante aux nouveaux_centres
        nouveaux_centres.append(centre_i)

    return nouveaux_centres

# Tests de la question 5
print(recalcul_centres(documents,[1, 0, 0, 1, 1],2))

# Question 6 : Algorithme des K moyennes
def k_moyennes(documents: list, k: int, centres_init: list) -> tuple:
    """
    Algorithme des k-moyennes.
    Paramètres : documents    — liste de vecteurs NumPy
                 k            — nombre de classes
                 centres_init — liste de k vecteurs NumPy (centres initiaux)
    Retour     : (labels, centres) — labels : list[int], centres : list[np.ndarray]
    """

    # Etape 1 : Affectation
    indices_centres_ = affectation(documents,centres_init)

    fin = False
    while fin == False:
        # Etape 2 : Calcul des nouveaux centres
        nouveaux_centres = recalcul_centres(documents,indices_centres_,k)

        # Etape 1 : Affectation
        indices_centres = affectation(documents,nouveaux_centres)

        if indices_centres == indices_centres_:
            fin = True
        else:
            indices_centres_ = indices_centres

    return (indices_centres,nouveaux_centres)


# Vérification question 6
labels, centres = k_moyennes(documents, k=2,
                             centres_init=[documents[1].copy(), documents[4].copy()])
print('\nLabels finaux :', labels)
print('Centres finaux :', centres)

# Question 7
# Centres initiaux pour k-moyennes (un par groupe)
centres_init = [
    documents_grands[0],   # groupe sciences
    documents_grands[4],   # groupe histoire
    documents_grands[8],   # groupe sport
]
# k-moyennes
labels_km, centres_km = k_moyennes(documents_grands, 3, centres_init)
print('\nLabels finaux doc_grands:', labels_km)
print('Centres finaux doc_grands:', centres_km)

############################
# ALGORITHME SINGLE-PASS
############################

# Question 10 : Fonction dist_max
def dist_max(di: np.ndarray, centres: list, theta: float) -> bool:
    """
    Teste si di est plus loin que theta de TOUS les centres existants.
    Paramètres : di      — vecteur NumPy du document courant
                 centres — liste des centres de classe courants
                 theta   — seuil de distance
    Retour     : bool — True si di doit créer une nouvelle classe
    """

    plus_loin = True

    for centre in centres:
        if delta(di,centre) <= theta:
            return False

    return plus_loin

# Tests
print("\n")
c_init = [documents[1]]
print(dist_max(documents[0], c_init, 5.0))  # Attendu : True  (delta(d1,c2)=6)
print(dist_max(documents[2], c_init, 5.0))  # Attendu : False (delta(d3,c2)=2)


# Question 11 : Fonction dist_min
def dist_min(di: np.ndarray, centres: list) -> int:
    """
    Retourne l'indice du centre le plus proche de di.
    Paramètres : di      — vecteur NumPy
                 centres — liste de vecteurs NumPy
    Retour     : int — indice ℓ tel que δ(di, centres[ℓ]) est minimal
    """

    distances= [delta(di,centres[i]) for i in range(len(centres))]

    return distances.index(min(distances))

# Tests
print("\n")
print(dist_min(documents[0],documents))
print(dist_min(documents[1],documents))
print(dist_min(documents[4],documents))

# Question 12 : Fonction recalcul_centre_sp
def recalcul_centre_sp(centres: list, l: int, classe_l: list) -> list:
    """
    Recalcule le centre cₗ après ajout d'un document à Aₗ.
    Paramètres : centres  — liste des centres courants (modifiée en place)
                 l        — indice de la classe à mettre à jour
                 classe_l — liste des vecteurs NumPy de la classe Aₗ
    Retour     : list — centres mis à jour
    """

    # Dimension des vecteurs
    p=len(centres[0])

    # Initialise la moyenne à 0
    moyenne = np.array([0 for i in range(p)])

    # Calcul du centre
    for doc in classe_l:
        moyenne = moyenne + doc
    moyenne = moyenne / len(classe_l)

    # Assigne le nouveau centre
    centres[l] = moyenne

    return centres

# Tests
print("\n")
centres = [documents[0], documents[1]]
classes = [[documents[0]], [documents[1],documents[2]]]
print(recalcul_centre_sp(centres,1,classes[1]))

# Question 13 : Algorithme Single-Pass
def single_pass(documents: list, theta: float) -> tuple:
    """
    Algorithme Single Pass.
    Paramètres : documents — liste de vecteurs NumPy
                 theta     — seuil de distance pour créer une nouvelle classe
    Retour     : (classes, centres)
                   classes : list[list[np.ndarray]] — classes[k] = liste des docs de Aₖ₊₁
                   centres : list[np.ndarray]       — centres[k] = centre de Aₖ₊₁
    """
    # Initialisation
    centres = [documents[0]]
    classes = [[documents[0]]]

    # Traite tous les documents les uns après les autres
    # en partant du premier qui n'a pas été classé
    for i in range(1,len(documents)):
        # Document courant di
        di = documents[i]

        # Si le document courant di est plus éloigné
        # des centres existants que theta
        if dist_max(di,centres,theta) == True:
            # Alors ajoute ce document à la nouvelle classe
            classes.append([di])
            # Ajoute le nouveau centre avec cj=di
            centres.append(di)

        # Sinon cherche le centre le plus proche
        # Et ajoute le document courant à la classe correspondante
        # Et met à jour le centre
        else:
            indice_centre_plus_proche = dist_min(di,centres)
            classes[indice_centre_plus_proche].append(di)
            recalcul_centre_sp(centres,indice_centre_plus_proche,classes[indice_centre_plus_proche])

    return centres, classes

# Tests
print("\nTest de l'algorithme Single-pass")
centres, classes = single_pass(documents,5.0)
print("Centres :",centres)
print("Classes: ",classes)